import collections
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        right_index = 0
        left_index = 0
        stack = collections.deque([s[i] for i in range(length)])
        word = collections.deque()
        while right_index < length:
            if stack[-1] == ' ':
                if word:
                    for item in word:
                        stack.insert(left_index, item)
                        left_index += 1
                    stack.insert(left_index, ' ')
                    left_index += 1
                    word = collections.deque()
                stack.pop()
                right_index += 1
            else:
                w = stack.pop()
                word.appendleft(w)
                right_index += 1
        if word:
            for item in word:
                stack.insert(left_index, item)
                left_index += 1
            stack.insert(left_index, ' ')
            left_index += 1
        stack.pop()
        return ''.join(stack)


data = Solution()
s = "a good   example"
print(data.reverseWords(s))
s = "the sky is blue"
print(data.reverseWords(s))
s = "  hello world  "
print(data.reverseWords(s))
s = "EPY2giL"
print(s)